package com.cat.dataStructure03;

import java.util.*;

/**
*   @description https://leetcode.cn/problems/least-number-of-unique-integers-after-k-removals/
*   @author 曲大人的喵
*   @create 2025/11/20 21:11
*   @since JDK17
*/

public class Solution95 {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (var x : arr) {
            map.merge(x, 1, Integer::sum);
        }
        int ans = 0;
        List<Integer> list = new ArrayList<>(map.values());
        Collections.sort(list, (a, b) -> a - b);
        for (int i = 0; i < list.size() && k >= list.get(i); i++) {
            k -= list.get(i);
            ans++;
        }
        return ans;
    }
}
